package me.qingy.old.binary_search;

import java.util.Arrays;

/**
 * @author qingy
 * @since 2021/1/28
 */
public class BinarySearch {

    /**
     * 时间复杂度：O(logn)
     */
    public static int binarySearch(int[] nums, int key) {
        // 双指针
        int l = 0;
        int r = nums.length - 1;

        if (key < nums[l] || key > nums[r])
            return -1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] < key)
                l = mid + 1;
            else if (nums[mid] > key)
                r = mid - 1;
            else
                return mid;
        }

        return -1;
    }

    /**
     * 二分查找的递归实现
     * 随着递归深度增加，调用栈在返回之前无法退出
     * 空间复杂度：O(logn)
     * 时间复杂度：O(logn)
     */
    public static int binarySearch(int[] nums, int key, int l, int r) {
        if (key < nums[l] || key > nums[r] || l > r)
            return -1;

        int mid = l + ((r - l) >> 1);
        if (nums[mid] < key)
            return binarySearch(nums, key, mid + 1, r);
        else if (nums[mid] > key)
            return binarySearch(nums, key, l, mid - 1);
        else
            return mid;
    }

    public static void main(String[] args) {
        int[] array = {3, 9, 10, 20, 55, 110};
        System.out.println(binarySearch(array, 11));
        System.out.println(binarySearch(array, 11, 0, array.length - 1));
        System.out.println(Arrays.binarySearch(array, 11));
    }

}
